package question.solution5;

import question.SolutionTemplate;

import java.util.HashMap;
import java.util.Map;

public class Solution5 implements SolutionTemplate {

    public String longestPalindrome(String s) {
        if(s.length() == 0){
            return null;
        }
        String longestString = s.substring(0,1);
        int maxLength = 1;
        boolean[][] palJudgeArr = new boolean[s.length()][s.length()];
        for(int j=0;j<s.length();j++){
            for(int i=0;j>=i;i++){
                if(i==j){
                    palJudgeArr[i][j] = true;
                }else if(i == j-1){
                    palJudgeArr[i][j] = s.charAt(i) == s.charAt(j);
                }else{
                    palJudgeArr[i][j] = palJudgeArr[i+1][j-1] && (s.charAt(i) == s.charAt(j));
                }
                if(palJudgeArr[i][j] && j-i+1 > maxLength){
                    longestString = s.substring(i,j+1);
                    maxLength = j-i+1;
                }
            }
        }
        return longestString;
    }

    @Override
    public void test() {

        System.out.println(longestPalindrome("babad"));
    }

}
